package com.cg.offer;

import org.junit.Test;

/**
 * 剑指Offer 51.数组中的逆序对
 *
 * @program: LeetCode->Offer_51
 * @author: cg
 * @create: 2022-04-07 23:22
 **/
public class Offer_51 {

    @Test
    public void test51() {
        System.out.println(reversePairs(new int[]{7, 5, 6, 4}));
    }

    /**
     * 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
     * <p>
     * 示例 1:
     * 输入: [7,5,6,4]
     * 输出: 5
     * <p>
     * 限制：
     * 0 <= 数组长度 <= 50000
     *
     * @param nums
     * @return
     */
    public int reversePairs(int[] nums) {
        this.nums = nums;
        tmp = new int[nums.length];
        return mergeSort(0, nums.length - 1);
    }

    int[] nums, tmp;

    private int mergeSort(int l, int r) {
        // 终止条件
        if (l >= r) {
            return 0;
        }
        // 递归划分
        int m = (l + r) / 2;
        int res = mergeSort(l, m) + mergeSort(m + 1, r);
        // 合并阶段
        int i = l, j = m + 1;
        for (int k = l; k <= r; k++) {
            tmp[k] = nums[k];
        }
        for (int k = l; k <= r; k++) {
            if (i == m + 1) {
                nums[k] = tmp[j++];
            } else if (j == r + 1 || tmp[i] <= tmp[j]) {
                nums[k] = tmp[i++];
            } else {
                nums[k] = tmp[j++];
                // 统计逆序对
                res += m - i + 1;
            }
        }
        return res;
    }
}
